package main

import (
	"bufio"
	"errors"
	"flag"
	"fmt"
	"math"
	"math/rand"
	"os"
	"regexp"
	"sort"
	"strconv"
	"strings"
	"time"
)

type lineInfo struct {
	lineNO uint
	value  float64
}

type lines []lineInfo

func (l lines) Len() int {
	return len(l)
}

func (l lines) Swap(i, j int) {
	l[i], l[j] = l[j], l[i]
}

func (l lines) Less(i, j int) bool {
	return l[i].value > l[j].value
}

//used for save the global test information
type gaConfig struct {
	programe        string
	loes, lofs      []int
	nots, noes, nof int
	casesPass       [][]uint64
	casesFailed     [][]uint64
	onesFromPass    []int
	onesFromFailed  []int
	compareValue    lines
}

var dataFilePath, ffName *string
var config *gaConfig

//called when loaded the package
func init() {
	dataFilePath = flag.String("file", "compressed_coverage_matrix.txt", "Use -file <filesource>")
	ffName = flag.String("ff", "1", "User -file <ffname>")
}

//init global test configuration
func initConfig(filepath string) (config *gaConfig, err error) {

	defer func() {
		if e := recover(); e != nil {
			fmt.Println(e)
			err = errors.New("resolve cofiguration error")
		}
	}()

	config = new(gaConfig)

	inputFile, err := os.Open(filepath)
	if err != nil {
		panic("读取数据文件失败")
	}
	defer inputFile.Close()

	scanner := bufio.NewScanner(inputFile)

	//regex for extract massive test case data
	re := regexp.MustCompile(`#CASE#(\d{5})#R(\d{1})# ([\d,\s]*)`)

Loop:
	for {
		scanner.Scan()
		v := strings.Split(scanner.Text(), " ")
		switch v[0] {
		case "#Ver_#":
			config.programe = v[1]
		case "#NOTS#":
			config.nots, err = strconv.Atoi(v[1])
		case "#LOES#":
			config.loes = make([]int, len(v)-1)
			for i, s := range v[1:] {
				config.loes[i], err = strconv.Atoi(s)
			}
		case "#NOES#":
			config.noes, err = strconv.Atoi(v[1])
			config.onesFromPass = make([]int, config.noes)
			config.onesFromFailed = make([]int, config.noes)
		case "#NOF_#":
			config.nof, err = strconv.Atoi(v[1])
		case "#LOFS#":
			config.lofs = make([]int, len(v)-1)
			for i, s := range v[1:] {
				config.lofs[i], err = strconv.Atoi(s)
			}
		default:
			submatches := re.FindStringSubmatch(scanner.Text())
			if submatches == nil || len(submatches) < 4 {
				break Loop
			} else if submatches[2] == "1" {
				// displayByteArray(&Record{stringToByteArray(submatches[3], config.noes), 0}, config.noes, config.lofs)
				//fmt.Println(submatches[3])
				config.casesFailed = append(config.casesFailed, stringToByteArray(submatches[3], config, false))
			} else if submatches[2] == "0" {
				//fmt.Println(submatches[3])
				// displayByteArray(&Record{stringToByteArray(submatches[3], config.noes), 0}, config.noes, config.lofs)
				config.casesPass = append(config.casesPass, stringToByteArray(submatches[3], config, true))
			}
		}
	}

	config.compareValue = make(lines, config.noes)
	if len(config.casesFailed) > 0 && len(config.casesPass) > 0 {
		for i := 0; i < config.noes; i++ {
			//fmt.Println(i, " ", config.onesFromFailed[i], " ", float64(config.noes), " ",float64(config.onesFromPass[i]), " ", float64(len(config.onesFromPass)), " ",float64(config.onesFromFailed[i]) / float64(len(config.casesFailed)),  " ", " ")
			config.compareValue[i].lineNO = uint(i)
			if config.onesFromPass[i] == 0 && config.onesFromFailed[i] == 0 {
				config.compareValue[i].value = 0
			} else {
				// Using Tarantula
				// config.compareValue[i].value = float64(config.onesFromFailed[i]) / float64(len(config.onesFromFailed)) / (float64(config.onesFromPass[i]) / float64(len(config.onesFromPass)) + float64(config.onesFromFailed[i]) / float64(len(config.casesFailed)))
				// using Ochiai
				config.compareValue[i].value = float64(config.onesFromFailed[i]) / math.Sqrt(float64(len(config.casesFailed))*(float64(config.onesFromFailed[i])+float64(config.onesFromPass[i])))
				
			}
		}
	}

	return config, nil
}

//generate random uint64 number cause go doesn't support this
func randomUint64() uint64 {
	return uint64(rand.Int63()<<1 | rand.Int63n(2))
}

//generate random []uint64 with fix size
func randomParent(size int) []uint64 {
	rand.Seed(time.Now().UnixNano())
	var result []uint64

	for i := 0; i < size/64; i++ {
		result = append(result, randomUint64())
	}

	if size%64 > 0 {
		appendix := randomUint64()
		offset := uint(64 - (size % 64))
		appendix = (appendix << offset) >> offset
		result = append([]uint64{appendix}, result...)
	}

	return result
}

func haveSex(father []uint64, mother []uint64, fixSize int) (son []uint64, girl []uint64) {
	son = make([]uint64, len(father))
	girl = make([]uint64, len(father))
	for i := 0; i < len(father); i++ {
		//inhert from father
		son[i] = father[i]
		girl[i] = mother[i]
		//different parents
		if (father[i] ^ mother[i]) > 0 {
			//iter to find the different pos
			for pos := uint64(1); pos > 0; pos <<= 1 {
				//found pos
				if ((father[i] ^ mother[i]) & pos) > 0 {
					// fmt.Printf("%065s\n", strconv.FormatUint(pos, 2))
					if rand.Intn(100) < 70 {
						son[i] ^= pos
						girl[i] ^= pos
					}
				}
			}
			// fmt.Println("")
		}
	}

	//mutate for 0.1% chance
	if rand.Intn(100) < 5 {
		var randomFactor uint = uint(rand.Intn(fixSize))
		var mutatePos = uint(len(son)) - 1 - (randomFactor >> 6)
		var mutateFactor = uint64(1 << (randomFactor % 64))
		son[mutatePos] ^= mutateFactor

		randomFactor = uint(rand.Intn(fixSize))
		mutatePos = uint(len(son)) - 1 - (randomFactor >> 6)
		mutateFactor = uint64(1 << (randomFactor % 64))
		girl[mutatePos] ^= mutateFactor
	}

	return son, girl
}

//calculate the fitness value for one record
func fitness(r []uint64, size int, casesSuccess [][]uint64, casesFailed [][]uint64) (fitValue float64) {
	switch *ffName {
	case "1":
		return OurFitness(r, size, casesSuccess, casesFailed)
	case "2":
		return LinearFitness(r, size, casesSuccess, casesFailed)
	}
	return LinearFitness(r, size, casesSuccess, casesFailed)
}

//parse string to generate []uint64
func stringToByteArray(s string, c *gaConfig, pass bool) (result []uint64) {
	fixsize := c.noes
	result = make([]uint64, 0)
	var buffer uint64
	var count = 0
	if fixsize%64 != 0 {
		count = 64 - fixsize%64
	}
	var i = 0
	for _, b := range s {
		switch b {
		case 48:
			buffer = buffer << 1
			i++
			count++
		case 49:
			if pass {
				c.onesFromPass[i] += 1
			} else {
				c.onesFromFailed[i] += 1
			}
			i++
			buffer = (buffer << 1) | 1
			count++
		}
		if count > 0 && count%64 == 0 {
			result = append(result, buffer)
			buffer = 0
			count = 0
		}
	}
	// if buffer%64 != 0 {
	// result = append(result, buffer)
	// }
	return result
}

//print out []uint64 with fix width
func displayByteArray(r *Record, fixed int, col []int) {
	// fmt.Printf("Value: %f，genetic byte: ", r.fitvalue)
	fmt.Printf("Value2: %f\n", r.fitvalue)
	// ia := r.detail
	// result := ""
	// for _, i := range ia {
	// 	fmt.Printf("%064s", strconv.FormatUint(i, 2))
	// 	result = result + " " + strconv.FormatUint(i, 2)
	// }
	// fmt.Println()

	// for i := 0; i < len(col); i++ {
	// 	pos := col[i]
	// 	if fixed%64 != 0 {
	// 		pos += 64 - fixed%64
	// 	}
	// 	fmt.Println(" bit value: ", r.detail[pos/64]&(1<<uint(63-(pos%64))))
	// }
}

func isMatchErrorLine(r *Record, fixed int, errorLines []int) bool {

	found := false
	for i := 0; i < len(errorLines) && !found; i++ {
		pos := errorLines[i]
		if fixed%64 != 0 {
			pos += 64 - fixed%64
		}
		found = (r.detail[pos/64] & (1 << uint(63-(pos%64)))) > 0
	}
	// fmt.Println(" bit value: ", r.detail[pos/64]&(1<<uint(63-(pos%64))))
	return found
}

func main() {
	//parse the input
	flag.Parse()

	//init config from input file
	config, _ = initConfig(*dataFilePath)

	// fmt.Println("Test Cases File loaded! config: ", config)
	fmt.Println(strings.Repeat("*", 80))

	//print the line info before sort
	for i := 0; i < len(config.compareValue); i++ {
		fmt.Println(config.compareValue[i], " ")
	}
	fmt.Println()

	//return

	var parentGroupSize = 500
	// var firstClassGroup = parentGroupSize * 4 / 10
	var vectorSize = config.noes
	var childSize = 1000
	var geneCounts = 150
	var yuzhi = 50
	fmt.Println("group size:", parentGroupSize)

	start := time.Now()
	var result []uint
	//for i := 0; i < 30; i++ {
		result = gaCore(parentGroupSize, vectorSize, config, geneCounts,  childSize, yuzhi)
		fmt.Print("result=", result, "\n")
	//}
	//for i, v := range result{
	//	fmt.Print(i, " : " , v)
	//}
	//result /= 30
	//fmt.Println("result: ", result)
	fmt.Println("Generating Random Parent Group time: ", time.Since(start))

}

func gaCore(parentGroupSize int, vectorSize int, config *gaConfig, geneCounts, childSize, yuzhi int) []uint {
	//random init parentGroup
	heap := GAHeap{data: make([]Record, parentGroupSize), size: parentGroupSize}
	for i := 0; i < parentGroupSize; i++ {
		gene := randomParent(vectorSize)
		heap.insert(Record{gene, fitness(gene, vectorSize, config.casesPass, config.casesFailed)})
	}

	//start to create next generation
	nextGeneration := make([]Record, 2*childSize)
	bestValue := .0
	geneCounts  = 0
	for {   //遗传代数
		for i := 0; i < childSize; i++ {    //每一代生多少孩子
			father, mother := heap.randomPair()
			boy, girl := haveSex(father.detail, mother.detail, vectorSize)
			//保存孩子
			nextGeneration[2*i] = Record{boy, fitness(boy, vectorSize, config.casesPass, config.casesFailed)}
			nextGeneration[2*i+1] = Record{girl, fitness(girl, vectorSize, config.casesPass, config.casesFailed)}
		}
		//检查并替换保留优秀的孩子
		for i := 0; i < 2*childSize; i++ {
			heap.checkAndExchange(nextGeneration[i])
		}
		r := heap.peekTop()
		// fmt.Printf("best: %f\n", bestValue)
		fmt.Printf("%d better: %f\n\n", geneCounts, r.fitvalue)
		// fmt.Println("grow", r.fitvalue - bestValue)
		if r.fitvalue - bestValue < 0.0001 {
			if yuzhi == 0{
				break
			}else{
				yuzhi--
			}
		}
		bestValue = r.fitvalue
		// fmt.Printf("%d better: %f\n\n", geneCounts, r.fitvalue)
		// displayByteArray(&r, vectorSize, config.lofs)
		geneCounts++
	}

	//store all records from heap to array
	recordsAfterFound := make([]Record, parentGroupSize)
	for i := parentGroupSize - 1; i >= 0; i-- {
		r := heap.getAndRemoveTop()
		//displayByteArray(&r, vectorSize, config.lofs)
		//if isMatchErrorLine(&r, vectorSize, config.lofs) {
		//	recordsAfterFound = []Record{}
		//}
		recordsAfterFound[i] = r
		//recordsAfterFound = append(recordsAfterFound, r)
	}
	displayByteArray(&recordsAfterFound[0], vectorSize, config.lofs)

	//store checking order for code line
	result := make([]lineInfo, 0)
	codeCoverage := make([]bool, vectorSize)
	//index := 0

	for _, r := range recordsAfterFound {
		for i := len(r.detail) - 1; i >= 0; i-- {
			var offset uint = 0
			tmp := make(lines, 0)
			for offset < 64 {
				if (1<<offset)&r.detail[i] > 0 {
					lineNo := uint(vectorSize) - 1 - offset - uint(((len(r.detail) - 1 - i) << 6))
					if !codeCoverage[lineNo] {
						codeCoverage[lineNo] = true
						tmp = append(tmp, lineInfo{lineNo, config.compareValue[lineNo].value})
					}
				}
				offset++
			}
			sort.Sort(tmp)
			result = append(result, tmp...)
			//for j:= 0; j < len(tmp); j++{
			//	result[index] = tmp[j]
			//	index++
			//}
		}
		//fmt.Println(result)
	}

	remainRecords := make(lines, 0)
	for i, v := range codeCoverage {
		if !v {
			remainRecords = append(remainRecords, config.compareValue[i])
		}
	}
	sort.Sort(remainRecords)
	//fmt.Println(len(result))
	result = append(result, remainRecords...)
	lines := make([]uint, vectorSize)
	for i := 0; i < len(result); i++ {
		lines[i] = result[i].lineNO
	}
	return lines
	//fmt.Println(result)

	////calculate the ones need search before get the right match
	//ss := vectorSize >> 6
	//if vectorSize != vectorSize << 6 {
	//	ss++
	//}
	//if !isMatchErrorLine(&recordsAfterFound[0], vectorSize, config.lofs) {
	//	fmt.Println("not found")
	//	return float32(vectorSize);
	//}
	//
	//ones := make([]uint64, ss)
	//for i := 0; i < len(recordsAfterFound); i++ {
	//	for j := 0; j < ss; j++ {
	//		ones[j] |= recordsAfterFound[i].detail[j]
	//	}
	//	//displayByteArray(&recordsAfterFound[i], vectorSize, config.lofs)
	//}
	//
	//sum := 0
	//for i := 0; i < ss; i++ {
	//	for ones[i] > 0 {
	//		sum++
	//		ones[i] &= ones[i] - 1
	//	}
	//}
	//
	//fmt.Println("ones: ", sum, " / ", vectorSize)
	//return result
}
